/**
 * 查找两个有序数列的中位数
 */
public class T4MiddleNumberOfTwoArrays {

    public static void main(String[] args) {
        T4MiddleNumberOfTwoArrays t4 = new T4MiddleNumberOfTwoArrays();
        System.out.println(t4.findMedianSortedArrays(new int[]{}, new int[]{1, 2, 3}));
    }

    /**
     *
     * 查早两个有序数组合并后的数组的中位数,本质上时寻找第n小,或者第n大数的过程/
     * 基本方法是,将数组用一根折线分割成两个部分,使得左右两边数量一样(总数组长度为偶数)或左边比右边多一个(为奇数),且确保左边的所有元素都比右边小.
     * 传统的方法时移动窗口,但移动窗口法可能在while循环中导致无线循环.而利用二分查找法来实现,可以保证循环的范围最终是收敛的.
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            //交换
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m = nums1.length;
        int n = nums2.length;
        //查找中位数时,左边n个元素即代表第n小或者第n大
        int totalLeft = (m + n + 1) / 2;//总数量为奇数时左边比右边多一个.
        int left = 0;
        int right = m;
        int i, j;
        while (left < right) {
            i = left + (right - left + 1) / 2;
            j = totalLeft - i;
            if (nums1[i - 1] > nums2[j]) {
                // 下一轮搜索的区间 [left, i - 1]
                right = i - 1;
            } else {
                // 下一轮搜索的区间 [i, right]
                left = i;
            }
        }

        i = left;
        j = totalLeft - i;

        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if (((m + n) % 2) == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
        }
    }
}
